package com.wang.sort3;

import com.wang.sort3.Demo08_GraphGenerator.Node;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: along
 * @Create: 2021/4/23
 * @Description:图的宽度优先遍历
 */
public class Demo09_BFS {
    //从node出发 宽度优先遍历
    public static void bfs(Node node) {
        if(node == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        HashSet<Node> set = new HashSet<>();//防止重复把节点放入队列
        queue.add(node);
        set.add(node);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            System.out.println(cur.value);
            for (Node next: cur.nexts
                 ) {
                if(!set.contains(next)) {//如果set中不存在该节点，才加入set和queue
                    set.add(next);
                    queue.add(next);
                }
            }
        }

    }
}
